//给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "abcabcbb"
//输出: 3 
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 
//
// 示例 2: 
//
// 
//输入: s = "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
// 
//
// 示例 3: 
//
// 
//输入: s = "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 5 * 10⁴ 
// s 由英文字母、数字、符号和空格组成 
// 
// Related Topics 哈希表 字符串 滑动窗口 👍 7625 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new LongestSubstringWithoutRepeatingCharacters().new Solution();
        solution.lengthOfLongestSubstring("abcabcbb");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // TODO 滑动窗口
        /*public int lengthOfLongestSubstring(String s) {
         *//*Map<Character, Integer> map = new HashMap();
    int left = 0, right = 0, maxLength = 0;
    for (; right < s.length(); right++) {
        if (map.containsKey(s.charAt(right))) {
            left = map.get(s.charAt(right));
        }
        maxLength = Math.max(maxLength, right - left + 1);
        map.put(s.charAt(right), right + 1);
    }
    return maxLength;*//*

            // 定义需要维护的变量，本题要求是最大长度，所以需要定义maxLength，该题又涉及去重，因此还需要一个哈希表
            Set<Character> set = new HashSet<>();
            int left = 0, right = 0, maxLength = 0;
            for (; right < s.length(); right++) {
                // 更新需要维护的变量（max_len和HashSet）
                while (set.contains(s.charAt(right))) {
                    set.remove(s.charAt(left));
                    left++;
                }
                maxLength = Math.max(right - left + 1, maxLength);
                set.add(s.charAt(right));
            }
            return maxLength;

            //1.定义需要维护的变量，本题要求是最大长度，所以需要定义max_len，该题又涉及去重，因此还需要一个哈希表
//        int max_len = 0, n = s.length();
//        Set<Character> set = new HashSet<Character>();
//        //2.定义窗口的首尾端（start，end），然后滑动窗口
//        int start = 0;
//        // int start = -1;
//        for(int end = 0; end < n; end++){
//
//            //3.更新需要维护的变量（max_len和HashSet）
//            while(set.contains(s.charAt(end))){
//                set.remove(s.charAt(start));
//                start++;
//            }
//            set.add(s.charAt(end));
//            max_len = Math.max(max_len, end - start + 1);
//        }
//        return max_len;
        }*/

        /*public int lengthOfLongestSubstring(String s) {
            Set<Character> set = new HashSet<>();
            int left = 0, right = 0, res = 0;
            while (right < s.length()) {
                char c = s.charAt(right);
                while (set.contains(c)) {
                    set.remove(s.charAt(left));
                    left++;
                }

                res = Math.max(res, right - left + 1);
                set.add(c);
                right++;
            }

            return res;
        }*/

        public int lengthOfLongestSubstring(String s) {
            Map<Character, Integer> window = new HashMap<>();
            int left = 0, right = 0, res = 0;

            while (right < s.length()) {
                char c = s.charAt(right);
                window.put(c, window.getOrDefault(c, 0) + 1);
                right++;

                // 如果right出现了重复，窗口的hash表出现重复，需要更新左边界
                while (window.get(c) > 1) {
                    // 更新左边界，注意使用while，一直更新，知道不出现重复
                    char c1 = s.charAt(left);
                    window.put(c1, window.getOrDefault(c1, 0) - 1);
                    left++;
                }

                // 需要在窗口更新完之后在计算，保证子串不重复
                res = Math.max(res, right - left);
            }

            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
